package cn.edu.nuaa.aadl2.generatorC.utils;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import org.osate.aadl2.DataImplementation;
import org.osate.aadl2.DataSubcomponent;
import java.util.Iterator;

/**
 * 对datatype进行拓扑排序
 * 否则构建的datatype头文件中的struct有可能报错： 引用结构体位于被引用结构体之前
 * */
public class sortDataType {
	public static Stack<Integer> stack;
	public static boolean[] datamark;

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	public static List<DataImplementation> sort(List<DataImplementation> datas) {
		if (datas == null)
			return null;
		stack = new Stack<>();
		datamark = new boolean[datas.size()];
		List<ArrayList<Integer>> LJMatrix = new ArrayList<>();
		List<DataImplementation> ans = new ArrayList<>();
		List<String> dataList = new ArrayList<>();
		for (int i = 0; i < datas.size(); i++) {
			datamark[i] = false;
			dataList.add(datas.get(i).getName());
		//	System.out.println("~~~~~~~~~~~~~" + datas.get(i).getName() + "~~~~~~~~~~~~`");
		}
		for (int i = 0; i < datas.size(); i++) {
			LJMatrix.add(new ArrayList<Integer>());
		}
		/*
		 * 
		 * @pram LJMatrix是DATA之间的邻接表
		 */
		for (int i = 0; i < datas.size(); i++) {
			DataImplementation data = datas.get(i);
			List<DataSubcomponent> LIST = data.getOwnedDataSubcomponents();
			for (DataSubcomponent dataSubcomponent : LIST) {
				if (dataList.contains(dataSubcomponent.getClassifier().getName()))
					LJMatrix.get(i).add(dataList.indexOf(dataSubcomponent.getClassifier().getName()));
			}
		}
		/*
		 * DFS 深度优先搜索逆后续排序==拓扑
		 */
		for (int i = 0; i < LJMatrix.size(); i++) {
			if (!datamark[i])
				dfs(LJMatrix, i);
		}
		Iterator<Integer> it = stack.iterator();
		while (it.hasNext()) {
			int next;
			next = it.next();
			ans.add(datas.get(next));
		//	System.out.println(next);
		}
		for (int i = 0; i < datas.size(); i++) {
			ArrayList<Integer> list = LJMatrix.get(i);
			for (Integer k : list) {
			}
		}
		return ans;
	}

	static public void dfs(List<ArrayList<Integer>> LJMatrix, int index) {
		datamark[index] = true;
		ArrayList<Integer> LIST = LJMatrix.get(index);
		for (int j = 0; j < LIST.size(); j++)
			if (!datamark[LIST.get(j)])
				dfs(LJMatrix, LIST.get(j));
		stack.push(index);
	}

}
